#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

// 一个由vector数组实现的小根堆
class minHeap
{
public:
	minHeap(){}
	~minHeap()
	{
		a.clear();
	}
	// 插入新的值后向上调整
	void push(int val)
	{
		a.push_back(val);
		adjustUp(a.size() - 1);
	}
	// 向上调整
	void adjustUp(int child)
	{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			// 调整逻辑是当儿子小于父亲时交换，然后继续向上
			if (a[child] < a[parent])
			{
				swap(a[child], a[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			// 不满足交换条件时，结束交换
			else
			{
				break;
			}
		}
	}
	// 删除堆顶元素的逻辑是：堆顶和堆底元素交换，堆顶元素弹出，并进行向下调整
	void pop()
	{
		assert(!empty());
		swap(a[0], a[a.size() - 1]);
		a.pop_back(); // 刚刚一直输出个没完是因为没有pop
		if (!empty())
		{
			adjustDown(0);
		}
	}
	// 向下调整
	void adjustDown(int parent)
	{
		int child = 2 * parent + 1;

		while (child < a.size())
		{
			// 找到左右子节点中较小的那个
			if (child + 1 < a.size() && a[child + 1] < a[child])
			{
				child++;
			}
			// 和父亲做比较，如果比父亲小，就交换，然后继续向下调整
			if (a[child] < a[parent])
			{
				swap(a[child], a[parent]);
				parent = child;
				child = 2 * parent + 1;
			}
			// 不满足条件时，结束调整
			else
			{
				break;
			}
		}
	}
	int getSize() const
	{
		return a.size();
	}
	bool empty()
	{
		return a.size() == 0;
	}
	int top()
	{
		assert(a.size() > 0);
		return a[0];
	}
private:
	vector<int> a;
};
